//设头结点为head


#include <stdlib.h>
#include <iostream>
template<class T>

struct ListNode{
    class Node* lLink;
    class Node* rLink;
    T data;
    int freq;
};

template<class T>
ListNode<T> *Locate(ListNode<T> *list, T x) {
    ListNode<T> *current=list;
    while (current->data !=x){
        current=current->rLink;
        if (current==list->rLink) return NULL; 
    }
    current->freq+=1;
    ListNode<T> *left=current->lLink;
    ListNode<T> *right=current->rLink;
    while (current->freq>left->freq)&&(list->rLink!=current){
        left->rLink=right;
        right->lLink=left;
        current->rLink=left;
        current->lLink=left->lLink;
        left->lLink->rLink=current;
        left->lLink=current;
        left=current->lLink;
        right=current->rLink;

    }
    return list;
}
